﻿//2653. 滑动子数组的美丽值
//给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。
//一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。
//请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。
//子数组指的是数组中一段连续 非空 的元素序列。


class Solution
{
public:
    int X = 0;
    int check(vector<int>& arr)
    {
        int x = X;
        for (int i = 0; i < 101; i++)
        {
            if (arr[i]) x -= arr[i];
            if (x <= 0)
            {
                if (i >= 50)
                    return 0;
                else
                    return i - 50;
            }
        }
        return 0;
    }

    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x)
    {
        X = x;
        int n = nums.size();
        vector<int> arr(101, 0);
        vector<int> ret(n - k + 1, 0);
        for (int i = 0; i < k; i++)
        {
            arr[nums[i] + 50]++;
        }
        ret[0] = check(arr);
        for (int i = 1; i <= n - k; i++)
        {
            arr[nums[i + k - 1] + 50]++;
            arr[nums[i - 1] + 50]--;
            ret[i] = check(arr);
        }
        return ret;
    }
};